package Demo2;

public class demo2 {
    public void shellSort(int[] array) {
        // 初始间隔设置为数组长度
        int gap = array.length;

        // 当间隔大于1时，继续进行希尔排序
        while (gap > 1) {
            // 更新间隔，通常将间隔除以2
            gap /= 2;

            // 使用当前间隔进行插入排序
            shellInsertSort(gap, array);
        }
    }

    private void shellInsertSort(int gap, int[] array) {
        // 从间隔后的第一个元素开始遍历
        for (int i = gap; i < array.length; i++) {
            // 保存当前要插入的元素
            int temp = array[i];
            // 从当前元素的前一个间隔位置开始向前检查
            int j = i - gap;

            // 将当前元素与前面间隔的元素进行比较
            // 如果前面间隔的元素大于当前元素，则将前面间隔的元素向后移动一位
            // 否则，找到正确的位置
            for (; j >= 0; j -= gap) {
                if (array[j] > temp) {
                    array[j + gap] = array[j]; // 移动元素
                } else {
                    break; // 找到插入位置
                }
            }
            // 将当前元素插入到找到的位置
            array[j + gap] = temp;
        }
    }
}
